package top.hkyzf.study.leetcode.dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 朱峰
 * @date 2022-1-30 17:40
 */
public class 三角形最小路径和_120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int k = triangle.size();
        if (k == 1) {
            return triangle.get(0).get(0);
        }
        int[][] f = new int[k][k];
        f[0][0] = triangle.get(0).get(0);
        label: for (int i = 1; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (j == 0) {
                    f[i][j] = f[i-1][j] + triangle.get(i).get(j);
                } else if (j == i) {
                    f[i][j] = f[i-1][j-1] + triangle.get(i).get(j);
                    continue label;
                } else {
                    f[i][j] = Math.min(f[i-1][j-1] + triangle.get(i).get(j), f[i-1][j] + triangle.get(i).get(j));
                }
            }
        }
        int result = f[k-1][0];
        for (int i = 1; i < k; i++) {
            if (result > f[k-1][i]) {
                result = f[k-1][i];
            }
        }
        return result;
    }

    @Test
    public void testMinimumTotal () {
        List<List<Integer>> teiangle = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(7);
        List<Integer> list4 = new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);
        teiangle.add(list1);
        teiangle.add(list2);
        teiangle.add(list3);
        teiangle.add(list4);
        System.out.println(minimumTotal(teiangle));
    }
}
